---
title: "1049. Last Stone Weight II"
created: 2025-12-18
---
# 1049. Last Stone Weight II

## 题目 [**1049. Last Stone Weight II**](https://leetcode.com/problems/last-stone-weight-ii/)

![[image-7d2d29e8.png]]

## 思路分析

![[image-56d266d1.png]]

选择任意两块互撞 要最后结果最小 显然是策略问题

那就想到dp和贪心 看看贪心能不能解出来：

模拟案例可知：

双指针 最大最小互撞 答案错误

优先队列最大两个互撞 也答案错误

看来不能简单贪心

确实有趣：

这道题的本质不是“消除”，而是**把石头分成两堆**。

当我们把石头 \(x\) 和 \(y\) 撞击得到 \(y-x\)，再拿去和 \(z\) 撞击得到 \(z-(y-x) = z-y+x\)...

你会发现，无论怎么撞，最终剩下的石头的重量，其实就是所有石头重量的加减组合：

\[Result = k\_1 \cdot s\_1 + k\_2 \cdot s\_2 + ... + k\_n \cdot s\_n\]

其中 \(k\) 只能是 \(+1\) 或 \(-1\)。

为了让结果最小（且 \(\ge 0\)），我们要把石头分成两堆（正数堆 \(P\) 和 负数堆 \(N\)），让它们的总和**差值最小**。

\[Target = \min(Sum\_P - Sum\_N)\]

这等价于：我们想从一堆石头里挑出一些，让它们的**总和尽可能接近（但不超过）总重量的一半**。

设所有石头总重为 sum，我们要找一个子集，其和 dp\_sum 最接近 sum / 2。

最终答案就是：

\[Answer = sum - 2 \times dp\\_sum\]

(解释：剩下的一半减去我们凑出来的一半)

这变成了一个经典的 **0/1 背包问题**：

- **背包容量**：`target = sum / 2`
- **物品**：每块石头的重量
- **价值**：每块石头的重量
- **目标**：往背包里装石头，装得越满越好（但不能撑破）。

将集合分成两个子集，使得差值最小”**或者**“加减号组合结果最小——通常都是 **0/1 背包问题** 的变体。

## 代码实现

```java
class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for(int stone : stones){
            sum+=stone;
        }
        int target = sum / 2;

        int[] dp = new int[target + 1];
        for(int stone : stones){
            for(int j=target; j >= stone ; j--){
                dp[j] = Math.max(dp[j],dp[j-stone]+stone);
            }
        }

        return sum - 2 * dp[target];
    }
}
```

## 同类题型

## 视频讲解